package sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {100, 250, 5, 6, 5, 85, 24, 14, 10, 52, 30, 34, 64};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }

    /*
        1.准备一个新的数组，和原数组长度相同
        2.处理的数据范围，最初从0到length-1(left到right)
        3.计算中间位置:mid = (left+right)/2
        4.递归排序左侧，范围:left到mid
        5.递归排序右侧，范围:mid+1到right
        6.左右两侧数据，合并，放到新数组
        7.新数组中的数据，复制会到原数组

        最简问题:left>=right 重合或交叉，只有一个值，或没有值
     */

    //归并排序
    private static void sort(int[] a) {
        int[] tmp = new int[a.length];
        sort(a, 0, a.length - 1, tmp);
    }

    private static void sort(int[] a, int left, int right, int[] tmp) {
        if (left >= right) { //最简问题:left>=right 重合或交叉，只有一个值，或没有值
            return;
        }
        int mid = (left + right) / 2; //计算中间位置
        sort(a, left, mid, tmp); //递归排序左侧
        sort(a, mid + 1, right, tmp); //递归排序右侧
        merge(a, left, mid, right, tmp); //把左侧排好序的数据和右侧排好序的数据，进行合并
    }

    private static void merge(int[] a, int left, int mid, int right, int[] tmp) {
        int i = left; //用来访问数组左侧范围:left到mid
        int j = mid + 1; //用来访问数组右侧范围:mid+1到right
        int k = left; //用来访问临时数组，范围:left到right
        while (i <= mid && j <= right) { //两侧都没有结束
            if (a[j] <= a[i]) { //原数组i和j位置比较大小，j位置的小值或相等值，放到临时数组的k位置
                tmp[k++] = a[j++];
            } else { //i位置的小值，放到临时数组的k位置
                tmp[k++] = a[i++];
            }
        }
        if (i <= mid) {
            //如果循环i没有结束，把i到mid范围的数据，复制到临时数组的k位置
            System.arraycopy(a, i, tmp, k, mid - i + 1); //原数组，原数组起始位置，目标数组，目标数组起始位置，数据的数量
//            while (i <= mid) { //把i到mid范围的数据，复制到临时数组的k位置,改为用while循环来实现
//                tmp[k++] = a[i++];
//            }
        } else {
            //如果循环j没有结束，把j到right范围的数据，复制到临时数组k的位置
            System.arraycopy(a, j, tmp, k, right - j + 1);
//            while (j <= right) { //把j到right范围的数据，复制到临时数组的k位置,改为用while循环来实现
//                tmp[k++] = a[j++];
//            }
        }
        //从tmp数组，把left到right范围已经有序的数据，复制回原数组
        System.arraycopy(tmp, left, a, left, right - left + 1);
//        for (k = left; k <= right; k++) { //从tmp数组，把left到right范围已经有序的数据，复制回原数组,改为用for循环实现
//            a[k] = tmp[k];
//        }
    }
}
